<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>heapSort</title>
</head>

<body>
    <script>
        function swap(arr, a, b) {
            let temp = arr[a]
            arr[a] = arr[b]
            arr[b] = temp
        }

        function maxheap_down(arr, start, length) {
            let temp = arr[start] //父节点
            let left = 2 * start + 1 //左子节点
            for (; left < length; left = 2 * left + 1) { //原left成为根节点，新left为新根节点的左子节点
                temp = arr[start]
                if (left + 1 < length && arr[left] < arr[left + 1]) {
                    left++ //left+1为右子节点，如果右边比较大，则用右边与根节点比较
                }
                if (temp < arr[left]) { //子节点与根节点比较
                    swap(arr, start, left) //交换根节点与较大孩子节点的位置
                } else {
                    break //什么也不做
                }

            }


        }

        function heapSort(arr) {
            //初始化大顶堆，从第一个非叶子节点开始
            for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
                maxheap_down(arr, i, arr.length)
            }
            //排序，每次循环将数组长度减一
            for (i = Math.floor(arr.length - 1); i > 0; i--) {
                swap(arr, 0, i)
                maxheap_down(arr, 0, i)
            }
            return arr
        }
        console.log(heapSort([9, 55, 4, 1, -2, 8, 0]))
    </script>
</body>

</html>